#pragma once

#include <stack>
#include <queue>
#include <math.h>
#include <stdexcept>
#include "IGraph.h"


typedef enum {
    NOT_PROCESSED = 0,
    IN_PROCESSING,
    PROCESSED,
} state;


class TopologicalSort {
public:
    TopologicalSort(int vertices_amount) : vertex_condition_(vertices_amount, NOT_PROCESSED) {}

    void StartProcessingVertex(int vertex) {
        vertex_condition_[vertex] = IN_PROCESSING;
    }

    void ProcessingEdge(int vertex, int incident_vertex) {
        try {
	    if (vertex_condition_[incident_vertex] == IN_PROCESSING) 
		throw std::logic_error("Error:: There is a circle");
        } catch (const std::exception& ex) {
            throw std::logic_error(std::string(ex.what()));
       }
    }

    void LeaveVertex(int vertex) {
        if (vertex_condition_[vertex] == PROCESSED) return;
        vertex_condition_[vertex] = PROCESSED;
        reversed_topological_order_.push_back(vertex);
    }

    std::vector<int> GetTopologicalOrder() const {
        std::vector<int> topological_order(reversed_topological_order_.begin(), reversed_topological_order_.end());
        std::reverse(topological_order.begin(), topological_order.end());
        return topological_order;
    }


private:
    std::vector<int> reversed_topological_order_;
    std::vector<state> vertex_condition_;
};


template <class Visitor>
void DFS(const IGraph& graph, Visitor& visitor) {
    std::vector<bool> visited(graph.GetNumberOfVertices(), false);
    for (int vertex = 0; vertex < graph.GetNumberOfVertices(); ++vertex) 
        if (!visited[vertex]) DFSImplementation(graph, visitor, visited, vertex);
}


template <class Visitor>
void DFSImplementation(const IGraph& graph, Visitor& visitor, std::vector<bool>& visited, int vertex_start) {
    std::stack<int> vertices_stack;
    vertices_stack.push(vertex_start);
    
    while (!vertices_stack.empty()) {
        int current_vertex = vertices_stack.top();
        
        if (!visited[current_vertex]) {
            visited[current_vertex] = true;
            visitor.StartProcessingVertex(current_vertex);

            std::vector<int> current_vertex_incidences = graph.GetIncidenceList(current_vertex);

            for (int i = 0; i < current_vertex_incidences.size(); ++i) {
                int next_incident_vertex = current_vertex_incidences[i];
                visitor.ProcessingEdge(current_vertex, next_incident_vertex);
                if (!visited[next_incident_vertex]) vertices_stack.push(next_incident_vertex);     
            }
        }
        else {
            visitor.LeaveVertex(current_vertex);
            vertices_stack.pop();
        }
    }
}

template <class Visitor>
void BFS(const IGraph& graph, Visitor& visitor) {
    std::vector<bool> visited(graph.GetNumberOfVertices(), false);
    for (int vertex = 0; vertex < graph.GetNumberOfVertices(); ++vertex) 
        if (!visited[vertex]) BFSImplementation(graph, visitor, visited, vertex);
}

template <class Visitor>
void BFSImplementation(const IGraph &graph, Visitor& visitor, std::vector<bool>& visited, int vertex_start) {
    std::queue<int> vertices_queue;
    vertices_queue.push(vertex_start);

    while(!vertices_queue.empty()) {
        int current_vertex = vertices_queue.front();
	vertices_queue.pop();
	visitor.StartProcessingVertex(current_vertex);	

	std::vector<int> current_vertex_incidences = graph.GetIncidenceList(current_vertex);
        for (int i = 0; i < current_vertex_incidences.size(); ++i) {
	    int next_incident_vertex = current_vertex_incidences[i];
            visitor.ProcessingEdge(current_vertex, next_incident_vertex);
	    if (visited[next_incident_vertex]) continue;

	    visited[next_incident_vertex] = true;
	    vertices_queue.push(next_incident_vertex);    
	}       
    }
}
